#include <bits/stdc++.h>

#define N 10005

using namespace std;

struct edge{
    int to;
    int val;
};

vector <edge> G[N];
long long dis[N];
int n, m, s;
bool isfind[100000]; //是否最短

void addedge(int fr, int to, int dis){
    G[fr].push_back((edge){to, dis});
}

void dijkstra(int scr){
    dis[scr] = 0; //到自己距离为0
    //find[scr] = true;

    int from[N];
    for(int x = 1; x <= n; x++){
        int u = -1;
        for(int i = 1; i <= n; i++){
            if(!isfind[i] && (u == -1 || dis[u] > dis[i])){
                u = i;
            }
        }
        if(u == -1) break;
        isfind[u] = true;
        for(edge v: G[u]){
            if(dis[v.to] > dis[u] + v.val){
                dis[v.to] = dis[u] + v.val;
            }
        }
    }
}

int main(){
    cin >> n >> m >> s;
    //memset(dis, 127, sizeof(dis));
    for(int i = 1; i <= n+5; i++){
        dis[i] = 0x7fffffff;
    }
    int u, v, val;
    for(int i = 1; i <= m; i++){
        scanf("%d %d %d", &u, &v, &val);
        addedge(u, v, val);
    }
    dijkstra(s);
    for(int i = 1; i <= n; i++){
        cout << dis[i] << " ";
    }
    return 0;
}